import java.util.*;

// 力扣228. 汇总区间
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new ArrayList<>();
        if(nums.length==0){
            return ans;
        }
        int start = 0;
        StringBuilder s = new StringBuilder();
        s.append(nums[0]);
        for (int i = 0; i < nums.length; i++) {
            if (i == 0)
                continue;
            if (nums[i] != nums[i - 1] + 1) { // 连续中止
                if (i - 1 != start) { // 中止位置和起点相差不为1，说明至少一个数字
                    s.append("->");
                    s.append(nums[i - 1]);
                    ans.add(s.toString());
                } else { // 为1说明只有一个数字
                    ans.add(s.toString());
                }
                start = i;
                s = new StringBuilder();
                s.append(nums[i]);
            }
        }
        int n = nums.length;
        if (n - 1 != start) { // 最后再判断一下
            s.append("->");
            s.append(nums[n - 1]);
            ans.add(s.toString());
        } else {
            ans.add(s.toString());
        }
        return ans;
    }
}




// 力扣57. 插入区间
// 注意!!!
// 题目条件:给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals
class Solution1 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // 添加所有在newInterval之前的区间
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // 合并重叠的区间
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // 添加剩余的区间
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[result.size()][]);
    }
}


// 力扣452. 用最少数量的箭引爆气球
class Solution2 {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,(a, b)->{
            return Integer.compare(a[0], b[0]); // 注意不能用 a[0]-b[0] ，可能会溢出
        });
        Deque<int[]> queue = new LinkedList<>();
        queue.offer(points[0]);
        for(int i=1;i<points.length;i++){
            int[] temp = queue.pollLast();
            if(temp[1]>=points[i][0]){
                temp[1] = Math.min(temp[1],points[i][1]);
                temp[0] = points[i][0];
                queue.offer(temp);
            }else{
                queue.offer(temp);
                queue.offer(points[i]);
            }
        }
        return queue.size();
    }
}